home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C / Utilities / byacc 1.8.2 / closure.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-02-04  |  4.7 KB  |  294 lines  |  [TEXT/R*ch]
  1. #include "defs.h"
  2.  
  3. short *itemset;
  4. short *itemsetend;
  5. unsigned *ruleset;
  6.  
  7. static unsigned *first_derives;
  8. static unsigned *EFF;
  9.  
  10.  
  11. #if __STDC__
  12. static void set_EFF(void)
  13. #else
  14. static void set_EFF()
  15. #endif
  16. {
  17.     register unsigned *row;
  18.     register int symbol;
  19.     register short *sp;
  20.     register int rowsize;
  21.     register int i;
  22.     register int rule;
  23.  
  24.     rowsize = WORDSIZE(nvars);
  25.     EFF = NEW2(nvars * rowsize, unsigned);
  26.  
  27.     row = EFF;
  28.     for (i = start_symbol; i < nsyms; i++)
  29.     {
  30.     sp = derives[i];
  31.     for (rule = *sp; rule > 0; rule = *++sp)
  32.     {
  33.         symbol = ritem[rrhs[rule]];
  34.         if (ISVAR(symbol))
  35.         {
  36.         symbol -= start_symbol;
  37.         SETBIT(row, symbol);
  38.         }
  39.     }
  40.     row += rowsize;
  41.     }
  42.  
  43.     reflexive_transitive_closure(EFF, nvars);
  44.  
  45. #ifdef    DEBUG
  46.     print_EFF();
  47. #endif
  48. }
  49.  
  50.  
  51. #if __STDC__
  52. void set_first_derives(void)
  53. #else
  54. void set_first_derives()
  55. #endif
  56. {
  57.   register unsigned *rrow;
  58.   register unsigned *vrow;
  59.   register int j;
  60.   register unsigned mask;
  61.   register unsigned cword;
  62.   register short *rp;
  63.  
  64.   int rule;
  65.   int i;
  66.   int rulesetsize;
  67.   int varsetsize;
  68.  
  69.   rulesetsize = WORDSIZE(nrules);
  70.   varsetsize = WORDSIZE(nvars);
  71.   first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;
  72.  
  73.   set_EFF();
  74.  
  75.   rrow = first_derives + ntokens * rulesetsize;
  76.   for (i = start_symbol; i < nsyms; i++)
  77.     {
  78.       vrow = EFF + ((i - ntokens) * varsetsize);
  79.       cword = *vrow++;
  80.       mask = 1;
  81.       for (j = start_symbol; j < nsyms; j++)
  82.     {
  83.       if (cword & mask)
  84.         {
  85.           rp = derives[j];
  86.           while ((rule = *rp++) >= 0)
  87.         {
  88.           SETBIT(rrow, rule);
  89.         }
  90.         }
  91.  
  92.       mask <<= 1;
  93.       if (mask == 0)
  94.         {
  95.           cword = *vrow++;
  96.           mask = 1;
  97.         }
  98.     }
  99.  
  100.       vrow += varsetsize;
  101.       rrow += rulesetsize;
  102.     }
  103.  
  104. #ifdef    DEBUG
  105.   print_first_derives();
  106. #endif
  107.  
  108.   FREE(EFF);
  109. }
  110.  
  111.  
  112. #if __STDC__
  113. void closure(short *nucleus, int n)
  114. #else
  115. void closure(nucleus, n)
  116. short *nucleus;
  117. int n;
  118. #endif
  119. {
  120.     register int ruleno;
  121.     register unsigned word;
  122.     register unsigned mask;
  123.     register short *csp;
  124.     register unsigned *dsp;
  125.     register unsigned *rsp;
  126.     register int rulesetsize;
  127.  
  128.     short *csend;
  129.     unsigned *rsend;
  130.     int symbol;
  131.     int itemno;
  132.  
  133.     rulesetsize = WORDSIZE(nrules);
  134.     rsp = ruleset;
  135.     rsend = ruleset + rulesetsize;
  136.     for (rsp = ruleset; rsp < rsend; rsp++)
  137.     *rsp = 0;
  138.  
  139.     csend = nucleus + n;
  140.     for (csp = nucleus; csp < csend; ++csp)
  141.     {
  142.     symbol = ritem[*csp];
  143.     if (ISVAR(symbol))
  144.     {
  145.         dsp = first_derives + symbol * rulesetsize;
  146.         rsp = ruleset;
  147.         while (rsp < rsend)
  148.         *rsp++ |= *dsp++;
  149.     }
  150.     }
  151.  
  152.     ruleno = 0;
  153.     itemsetend = itemset;
  154.     csp = nucleus;
  155.     for (rsp = ruleset; rsp < rsend; ++rsp)
  156.     {
  157.     word = *rsp;
  158.     if (word == 0)
  159.         ruleno += BITS_PER_WORD;
  160.     else
  161.     {
  162.         mask = 1;
  163.         while (mask)
  164.         {
  165.         if (word & mask)
  166.         {
  167.             itemno = rrhs[ruleno];
  168.             while (csp < csend && *csp < itemno)
  169.             *itemsetend++ = *csp++;
  170.             *itemsetend++ = itemno;
  171.             while (csp < csend && *csp == itemno)
  172.             ++csp;
  173.         }
  174.  
  175.             mask <<= 1;
  176.             ++ruleno;
  177.         }
  178.     }
  179.     }
  180.  
  181.     while (csp < csend)
  182.     *itemsetend++ = *csp++;
  183.  
  184. #ifdef    DEBUG
  185.   print_closure(n);
  186. #endif
  187. }
  188.  
  189.  
  190.  
  191. #if __STDC__
  192. void finalize_closure(void)
  193. #else
  194. void finalize_closure()
  195. #endif
  196. {
  197.   FREE(itemset);
  198.   FREE(ruleset);
  199.   FREE(first_derives + ntokens * WORDSIZE(nrules));
  200. }
  201.  
  202.  
  203. #ifdef    DEBUG
  204.  
  205. #if __STDC__
  206. static void print_closure(int n)
  207. #else
  208. static void print_closure(n)
  209. int n;
  210. #endif
  211. {
  212.   register short *isp;
  213.  
  214.   printf("\n\nn = %d\n\n", n);
  215.   for (isp = itemset; isp < itemsetend; isp++)
  216.     printf("   %d\n", *isp);
  217. }
  218.  
  219.  
  220. #if __STDC__
  221. static void print_EFF(void)
  222. #else
  223. static void print_EFF()
  224. #endif
  225. {
  226.     register int i, j, k;
  227.     register unsigned *rowp;
  228.     register unsigned word;
  229.     register unsigned mask;
  230.  
  231.     printf("\n\nEpsilon Free Firsts\n");
  232.  
  233.     for (i = start_symbol; i < nsyms; i++)
  234.     {
  235.     printf("\n%s", symbol_name[i]);
  236.     rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars));
  237.     word = *rowp++;
  238.  
  239.     mask = 1;
  240.     for (j = 0; j < nvars; j++)
  241.     {
  242.         if (word & mask)
  243.         printf("  %s", symbol_name[start_symbol + j]);
  244.  
  245.         mask <<= 1;
  246.         if (mask == 0)
  247.         {
  248.         word = *rowp++;
  249.         mask = 1;
  250.         }
  251.     }
  252.     }
  253. }
  254.  
  255.  
  256. #if __STDC__
  257. void print_first_derives(void)
  258. #else
  259. void print_first_derives()
  260. #endif
  261. {
  262.   register int i;
  263.   register int j;
  264.   register unsigned *rp;
  265.   register unsigned cword;
  266.   register unsigned mask;
  267.  
  268.   printf("\n\n\nFirst Derives\n");
  269.  
  270.   for (i = start_symbol; i < nsyms; i++)
  271.     {
  272.       printf("\n%s derives\n", symbol_name[i]);
  273.       rp = first_derives + i * WORDSIZE(nrules);
  274.       cword = *rp++;
  275.       mask = 1;
  276.       for (j = 0; j <= nrules; j++)
  277.     {
  278.       if (cword & mask)
  279.         printf("   %d\n", j);
  280.  
  281.       mask <<= 1;
  282.       if (mask == 0)
  283.         {
  284.           cword = *rp++;
  285.           mask = 1;
  286.         }
  287.     }
  288.     }
  289.  
  290.   fflush(stdout);
  291. }
  292.  
  293. #endif
  294.